#ifndef UTIL_H
#define UTIL_H

#include <string>
#include <map>
#include <vector>
#include <deque>

#include <algorithm>

#include <mutex>

#include <stdexcept>
#include <cassert>

namespace scgi
{

template <typename T_>
std::string to_string(T_ i_)
{
	std::string result;
	result.reserve(24); // log10(2^64) = 1.84457442 * 10^19

	while(true)
	{
		result.append(1, i_ % 10 + '0');
		i_ /= 10;
		if(!i_) break;
	}
	std::reverse(result.begin(), result.end());

	return std::move(result);
}

template <typename T_>
std::string to_hex_string(T_ first_, T_ last_)
{
	std::string result;
	result.reserve((last_ - first_) * 2);

	while(first_ != last_)
	{
		unsigned char
			  ch = *first_++
			, hi = ch >> 4
			, lo = ch & 0xF;

		hi = (9 < hi) ? 'a' + (hi - 10) : '0' + hi;
		lo = (9 < lo) ? 'a' + (lo - 10) : '0' + lo;
		
		result.append(1, hi);
		result.append(1, lo);
	}

	return result;
}

unsigned long long to_uint_64(std::string string_);

unsigned int to_uint_32(std::string string_);

struct Time
{
	long long time;

	Time();
	Time(long long time_);

	void operator = (long long time_);

	long long to_int_64() const;

	std::string to_cookie_string() const;
	std::string to_http_date_string() const;

	operator bool () const;
	bool operator ! () const;
	bool operator < (Time rhs_) const;
	Time operator + (Time rhs_) const;
	Time operator - (Time rhs_) const;
	
private:
	static std::string to_four_string(unsigned short four_);
	static std::string to_two_string(unsigned short two_);
	static std::string to_week_string(unsigned short week_);
	static std::string to_month_string(unsigned short month_);

public:
	static Time seconds(long seconds_);
	static Time minutes(long minutes_);
	static Time hours(long hours_);
	static Time days(long days_);
};

// PHP style. see http://www.php.net/manual/en/function.urlencode.php
class URLEncoder
{
public:
	URLEncoder() { }

	template<typename T1_, typename T2_>
	void operator () (T1_ first_, T1_ last_, T2_ fn_)
	{
		char const tbl[16] = {
			  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
			, 'A', 'B', 'C', 'D', 'E', 'F' };

		while(first_ != last_)
		{
			unsigned char ch = *first_++;
			if(ch == '-' || ch == '_' || ch == '.'
				|| ('a' <= ch && ch <= 'z')
				|| ('A' <= ch && ch <= 'Z'
				|| ('0' <= ch && ch <= '9'))) { fn_(ch); continue; }
			if(ch == ' ') { fn_('+'); continue; }

			fn_('%');
			fn_(tbl[ch >> 4]);
			fn_(tbl[ch & 0xF]);
		}
	}

	template <typename T_>
	std::string operator () (T_ first_, T_ last_)
	{
		std::string result;
		result.reserve(256);
		operator()(first_, last_, [&](char ch_){ result.append(1, ch_); });
		return std::move(result);
	}
};

class URLDecoder
{
private:
	size_t state;
	unsigned char buffer;

public:
	URLDecoder() : state(0) { }

	template<typename T1_, typename T2_>
	void operator () (T1_ first_, T1_ last_, T2_ fn_)
	{
		unsigned char ch;
		switch(state)
		{
s0: case 0: state = 0; if(first_ == last_) return;
			ch = *first_++;
			if(ch == '%') goto s1;
			if(ch == '+') ch = ' ';
			fn_(ch);
			goto s0;
s1: case 1: state = 1; if(first_ == last_) return;
			buffer = code(*first_++);
case 2: state = 2; if(first_ == last_) return;
			ch = code(*first_++);
			fn_((buffer << 4) + ch);
			goto s0;
		}
	}

	template<typename T_>
	std::string operator () (T_ first_, T_ last_)
	{
		std::string result;
		result.reserve(256);
		operator()(first_, last_, [&](char ch_){ result.append(1, ch_); });

		state = 0; // reset.
		return std::move(result);
	}

private:
	unsigned char code(unsigned char ch_) const
	{
		if('0' <= ch_ && ch_ <= '9') return ch_ - '0';
		if('A' <= ch_ && ch_ <= 'F') return ch_ - 'A' + 10;
		if('a' <= ch_ && ch_ <= 'f') return ch_ - 'a' + 10;
		assert(false);
		return ch_;
	}
};

template <char Ch1_ = '=', char Ch2_ = '&'>
class Tokenizer
{
public:
	template <typename T1_, typename T2_>
	void operator () (T1_ first_, T1_ last_, T2_ fn_)
	{
		while(first_ != last_)
		{
			T1_ current = std::find(first_, last_, Ch1_);
			std::string key(first_, current);
			first_ = current;
			if(first_ != last_) ++first_;

			std::string value;
			if(first_ != last_)
			{
				current = std::find(first_, last_, Ch2_);
				value = std::string(first_, current);
				first_ = current;
			}
			fn_(std::move(key), std::move(value));

			if(first_ != last_) ++first_;
		}
	}
};

struct Cookie
{
	typedef std::map<std::string, std::string> table_type;
	typedef table_type::const_iterator const_iterator;

	table_type table;
	Time expires;
	std::string domain, path;
	bool secure;

	std::string get(std::string key_) const;
	void set(std::string key_, std::string value_);

	const_iterator begin() const;
	const_iterator end() const;

	template <typename T_>
	void assign(T_ first_, T_ last_)
	{
		while(first_ != last_)
		{
			URLDecoder decode;

			T_ current = std::find(first_, last_, '=');
			std::string key = decode(first_, current);
			first_ = current;
			if(first_ != last_) ++first_;

			std::string value;
			if(first_ != last_)
			{
				current = std::find(first_, last_, ';');
				value = decode(first_, current);
				first_ = current;
			}
			table[key] = value;

			if(first_ != last_) ++first_;
			if(first_ != last_ && *first_ == ' ') ++first_;
		}
	}

	std::string to_string() const;
};

std::string MD5(std::string string_);

template <typename T1_, typename T2_>
class CacheT
{
	struct Container
	{
		T1_ before, next;
		T2_ value;

		Container() { }
		Container(T1_ before_, T1_ next_, T2_ value_)
			: before(before_), next(next_), value(value_) { }
	};

public:
	typedef typename T1_ key_type;
	typedef typename T2_ value_type;
	typedef std::map<key_type, Container> table_type;

private:
	table_type table;
	key_type begin, end;

	std::mutex mutex;
	size_t max_size;

public:
	CacheT(size_t max_size_ = 1000) : max_size(max_size_) { assert(max_size); }

	size_t size()
	{
		mutex.lock();
		size_t result = table.size();
		mutex.unlock();
		return result;
	}

	void set(key_type key_, value_type value_)
	{
		mutex.lock();
		
		size_t table_size = table.size();

		if(max_size <= table_size)
		{
			table_type::iterator it1 = table.find(begin);
			begin = it1->second.next;
			table.erase(it1);
			table[begin].before = begin;
		}

		if(table_size == 0)
		{
			table[key_] = Container(key_, key_, value_);
			begin = key_;
		}
		else
		{
			table[end].next = key_;
			table[key_] = Container(end, key_, value_);
		}
		end = key_;

		mutex.unlock();
	}

	value_type get(key_type key_)
	{
		mutex.lock();
		value_type result = get_(key_);
		mutex.unlock();

		return result;
	}

private:
	value_type get_(key_type key_)
	{
		value_type result;

		table_type::const_iterator it1 = table.find(key_);
		if(it1 != table.end())
		{
			key_type
				  before = it1->second.before
				, next = it1->second.next;

			if(before == key_)
			{
				begin = next;
				table[next].before = next;
			}
			else if(end != key_) { table[before].next = next; }

			if(end == key_)
			{
				end = before;
				table[before].next = before;
			}
			else if(before != key_) { table[next].before = before; }

			result = it1->second.value;
			table.erase(it1);
		}

		return result;
	}
};

} // scgi

#endif // UTIL_H
